算法日记(2) —— 进制转换

对于一个 P 进制的数，如果要转换成 Q 进制，需要分为两步：

将 P 进制的数 x 转换成十进制数 y

若 P 进制数 x 为 $a_1a_2···a_n$，则 x 可以通过以下公式转换为十进制数 y：

$y = a_1*P^{n-1}+a_2*P^{n-2}+···+a_n$

而这个公式可以很容易用循环来实现：

int y = 0, product = 1;    //product在循环中会不断乘P，得到1、p、p^2、P^3···
while(x != 0) {
    y = y + (x % 10) * product;    //x % 10是为了每次获取x的个位数
    x = x / 10;    //去掉x的个位
    product = product * P;
}

将十进制数 y 转换成 Q 进制数 z

采用“除基取余法”——所谓的“基”，是指将要转换成的进制 Q，因此除基取余的意思就是每次将待转换数除以 Q，然后将得到的余数作为低位存储，而商则继续除以 Q 并重复上面的操作，最后当商为 0 时，将所有位从高到低输出就可以得到 z。

由此可以得到实现的代码：

int z[40], num = 0;    //数组z存放Q进制数y的每一位，num为位数
do {    //不使用while语句原因：如果十进制数y恰好等于0，使用while会直接跳出循环，导致结果出错
    z[num++] = y % Q;
    y = y / Q;
} while(y != 0);    //当商不为0时进行循环

这样 z 数组从高位 z[num - 1] 到低位 z[0] 即为 Q 进制 z，进制转换完成。

【PAT B1022】D 进制的 A+B

题目描述

1	输入两个非负十进制整数A和B以及D（进制数），输出A+B的D（1<D<11）进制数。

输入格式

1	在一行中依次给出三个整数A、B和D（进制数）。

输出格式

A+B的D进制数。

输入样例

123 456 8

输出样例

参考代码

#include<stdio.h>
int main() {
    int a, b, d;
    scanf("%d%d%d", &a, &b, &d);
    int sum = a + b;
    int ans[31], num = 0;    //ans存放D进制数的每一位
    do {    //进制转换
        ans[num++] = sum % d;
        sum /= d;
    } while(sum != 0);
    for(int i = num - 1; i >= 0; i--) {    //从高位到低位进行输出
        printf("%d", ans[i]);
    }
    return 0;
}